#include<bits/stdc++.h>

using namespace std;
using ll=long long;

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

/**
 * phi(n)=n*(1-1/p1)*(1-1/p2)....(1-1/pm)
 *
 * @param n
 * @return
 */
ll phi(ll n) {
    ll p = 2;
    ll tot = n;
    while (n > 1) {
        if (n % p == 0) {
            n /= p;
            tot /= p;
            tot *= p - 1;
            while (n % p == 0) {
                n /= p;
            }
        }

        p++;
    }
    return tot;
}

int main() {


    long long start = clock();
    cout << phi(2000000) << endl;
    long long end = clock();
    cout << (end - start) << endl;
    return 0;

}